import datastructure.Node;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/18 10:53
 * @description:
 */
public class LCR155 {
    public Node head = null;
    public Node pre = null;

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        traverse(root);
        pre.right = head;
        head.left = pre;
        return head;
    }

    public void traverse(Node node) {
        if (node == null) {
            return;
        }
        traverse(node.left);
        if (head == null) {
            head = node;
        }
        if (pre == null) {
            pre = node;
        } else {
            pre.right = node;
            node.left = pre;
            pre = node;
        }
        traverse(node.right);
    }

    public static void main(String[] args) {
        LCR155 lcr = new LCR155();
        Node root = Node.buildTree(new int[]{4, 2, 5, 1, 3});
        Node.printTree(root);
        Node head = lcr.treeToDoublyList(root);
        Node.printDoublyList(head);

    }
}
